The Multidimensional Knapsack Problem (MKP) is a typical multi-constraint combinatorial problem. In order to solve this problem, a Modified Binary Cuckoo Search (MBCS) algorithm was proposed. Firstly, with the help of classical binary code transformer, the Binary Cuckoo Search (BCS) algorithm was built; Secondly, the virus evolution mechanism and virus infection operation were introduced into the BCS. Specifically, on one hand, it made the position of bird's nest have mutation mechanism, which could improve the diversity of the population; on another hand, the main groups that consisted of nest position transmitted information cross the vertical generations and guided the global search, while the virus groups transfered evolutionary information cross the same generation through virus infection and guided the local search. These improved the convergence speed and decreased the probability of falling into the local optimum. Thirdly, the hybrid repair strategy for infeasible solutions was designed according to the characteristics of the MKP. At last, comparison experiments among the MBCS algorithm, Quantum Genetic Algorithm (QGA), Binary Particle Swarm Optimization (BPSO) algorithm and BCS algorithm were given on 15 different problems from ELIB and OR_LIB database. The experimental results show that the computational error and standard deviation of MBCS are less than 1% and 170, respectively, which shows the MBCS algorithm can achieve better solutions with good accuracy and robustness than QGA, BPSO and BCS algorithm. It is an effective algorithm in solving NP-hard problems such as the MKP.